/**
    插入排序

 */
#include<stdio.h>
const int numbers_size=8;
int numbers[]={49,38,65,97,76,13,27,49};
//挖坑法
void insertSort(int array[],int n){
    int i,j;
    //从左往右排序，第一个元素就一个，也就是自然有序，所以从第二个元素开始排
    for(int i=1;i<n;i++){
        if(array[i]<array[i-1]){//如果第array[i]比前一个小，那么应该让array[i]左移到对应的位置
            int key=array[i];
            //内层循环用来移动，第i个元素是要插入的元素，如果前面的元素比这个元素小，
            //就要往后移动一个位置（这个位置已经赋值给key保存起来了，被占用了也没关系）
            for(j=i-1;key<array[j];j--){
                array[j+1]=array[j];
            }
            array[j+1]=key;//for循环j--是每次循环之后做的，赋值需要j+1
        }
    }
}

void show(int array[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}

int main(void){
    insertSort(numbers,numbers_size);
    show(numbers,numbers_size);
}